package com.zwj.interview.数组;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入一个只包含0和1的数组，请问如何求0和1的个数相同的最长连续子数组的长度？
 * 例如，在数组[0，1，0]中有两个子数组包含相同个数的0和1，分别是[0，1]和[1，0]，它们的长度都是2，因此输出2
 */
public class ZeroAndOneEqualSubArrayCount {


    /**
     * 首先把输入数组中所有的0都替换成-1，那么题目就变成求包含相同数目的-1和1的最长子数组的长度。
     * 在一个只包含数字1和-1的数组中，如果子数组中-1和1的数目相同，那么子数组的所有数字之和就是0，
     * 因此这个题目就变成求数字之和为0的最长子数组的长度
     *
     * @param nums
     * @return
     * 可以在扫描数组时累加已经扫描过的数字之和。如果数组中前i个数字之和为m，
     * 前j个数字（j>i）之和也为m，那么从第i+1个数字到第j个数字的子数组的数字之和为0，这个和为0的子数组的长度是j-i
     * <p>
     * <p>
     * 如果扫描到数组的第j个数字并累加得到前j个数字之和m，那么就需要知道是否存在一个i（i＜j）使数组中前i个数字之和也为m。
     * 可以把数组从第1个数字开始到当前扫描的数字累加之和保存到一个哈希表中。由于我们的目标是求出数字之和为0的最长子数组的长度，
     * 因此还需要知道第1次出现累加之和为m时扫描到的数字的下标。因此，哈希表的键是从第1个数字开始累加到当前扫描到的数字之和，
     * 而值是当前扫描的数字的下标
     */
    public static int findMaxLength(int[] nums) {
        //前i个数字的和
        Map<Integer, Integer> sumToIndex = new HashMap<>();
        sumToIndex.put(0, -1);
        int sum = 0;
        int maxLength = 0;
        for (int i = 0; i < nums.length; ++i) {
            //碰到0的时候，将0转为-1，sumToIndex，记录的是前i个数字的和，其中和为键，i为值
            sum += nums[i] == 0 ? -1 : 1;
            //map中第一次出现和等于当前扫描到的下标数字的累加和，那么就可以找出这个长度了
            //存储每个前缀和第一次出现的下标,走到这里说明sumToIndex.containsKey(sum)到下标i之间就有为0的前缀和，
            //之前那些项的和再加上到i之间这些元素值相同，说明这段区间的这些元素的和为0
            /**
             *                     p1                           p2
             *   x x x x x x x x x  x  x   x   x    x   x   x    x   x   x  x  x   x   x
             *                     sum                          sum2
             *   如果说sum2在map中已经存在，那么就说明前面肯定已经有若干项的和sum=sum2,那么从p1到p2之间这些连续的元素和就为0,也就是i-map.get(sum)
             */
            if (sumToIndex.containsKey(sum)) {
                maxLength = Math.max(maxLength, i - sumToIndex.get(sum));
            } else {
                //前i项和作为键，最后一个下标作为值
                sumToIndex.put(sum, i);
            }
        }
        return maxLength;
    }

    /**
     *  本题本质上也是前缀和思想：
     *  我们使用prefixSums[i] 表示数组从下标0到下标i的子数组和
     *  如果说prefixSums[k]−prefixSums[j]=0 时，我们就得到一个长度为k-j
     *
     *
     *
     */

    public static void main(String[] args) {
        System.out.println(findMaxLength(new int[]{0, 1, 0}));
    }
}
